dos opciones:
1) si estas haciendo nat/mascarading solo vas a poder restringir por ips, no por usuario y contraseña.
2) si estas usando un proxy (como el squid), podes configurarlo para que valide con usuario y contraseña.
www.squid-cache.org. Aca te paso el parametro que necesitas agregar en la configuracion del squid:
Tag Name authenticate_program
Usage authenticate_program path/to/program path/to/passwdfile
Description
This tag is used to specify the command for the external authenticator. Such a program reads a line containing "username password" and replies "OK" or "ERR" in an endless loop. If you use an authenticator, make sure you have 1 acl of type proxy_auth. If you want to use the traditional proxy authentication, jump over to the ../auth_modules/NCSA directory and give
# make
# make install
The source for this program is included in the source distribution, in the auth_modules/NCSA directory. You should now have an ncsa_authprogram in the same directory where your squid binary lives. You may need to create a password file. If you have been using proxy authentication before, you probably already have such a file. You can get apache's htpasswd program from here. Pick a pathname for your password file. We will assume you will want to put it in the same directory as your Squid.conf.
Default authenticate_program none By default, the authenticator_program is not used
Example
authenticate_program /usr/local/squid/bin/ncsa_auth /usr/local/squid/etc/passwd
obtenido de:
http://squid.visolve.com/squid24s1/externals.htm 
