What should I ask a security consultant to see if they are legitimate or not?
I'm looking to hire someone to perform an assessment, but I'd like to make sure that someone is reputable first.
Asking for references is a reasonable start.
Another crude indicator is their visibility and track record at well-regarded conferences. If they are a speaker at Blackhat, RSA Security conference, WOOT, etc., that's often a good sign. (But lack of this kind of visibility does not necessarily mean they are unqualified. This is a very crude indicator, at best.)
You could also look at their track record of disclosed vulnerability reports, white papers, etc.
I would not pay too much attention to certifications. If their primary or only credential is a CISSP or similar certification, odds are that you are getting a low-level person. The value of a certification will depend upon the particular certification and the kind of work you are looking for the consultant to do.
For more details on what to read into certifications and their reputation, see the following threads: Professional certifications for IT Security; Web Security Certifications; International pentester certification; What are the basic certification course for beginners?; How useful is CISSP to a recent graduate?; CEH or GIAC - Which one should I pursue?; would preparing for CCNA add “significantly” to my knowledge as a penetration tester?.
Invent a scenario similar to the one you want them to work on, and get them to walk you through how they would tackle it. You'd want to assess their ability to understand the needs of your business as well as their technical understanding. The key factor would be whether they ask the right questions and give you the right answers.
For example, you might want someone to assess your e-commerce infrastructure, so your scenario might start with the question:
A good candidate would immediately start asking about the data involved, and the level of risk you're willing to tolerate. A bad candidate would get immediately proscriptive.
If they answer that to your satisfaction, or draw the information out of you, you can expand it to:
... etc. Ideally, in this scenario, you'd have a candidate who looks at wider issues than just IT - policies, procedures, staff training, backups and backup security all play a part as well as firewalls and IPS.
If you don’t have anyone available to challenge his or her technical expertise then I would say go the client references route. Ask for references - preferably from clients where they performed similar work.
References, references, and more references. From companies that are close to your size. You should call the reference and ask how the consultant did. Ask if they read your existing policies and procedures and made suggestions for improvements. As if they suggested industry best practices. The consultant having a speaking role at a conference doesn't factor at all into whether they can do the job. If they have presented at conferences or written books you should always ask for their book or slides or a recording of the talk and review that to see if they reference previous customers. Last thing you want is for them to be talking about your company (even anonymously) at the next conference.