Tente adicionar '-lcrypt' depois de qualquer objeto usado na vinculação; Eu tive alguns casos em que o gcc iria reclamar sobre o crypt se o -crypt não estivesse perto do final da lista de links.
Em outras palavras, tente algo como:
gcc -D FOO -D BAR -W -Wall -pedantic -O2 foo.o bar.o -lnsl -lcrypt -o baz
ao contrário de
gcc -D FOO -D BAR -W -Wall -pedantic -O2 -lnsl -lcrypt foo.o baz.o -o baz