This past week, Affinity Gaming, a Las Vegas casino company, filed suit against security firm Tripwire for "woefully inadequate" forensics in response to work they did when they were retained to investigate a network breach. Tripwire has a strong reputation, and it is early in the legal process to draw any conclusions. It should give you pause however to consider how you would choose a security consultant, should you have the need. Sadly, more and more businesses and organizations now find themselves in need of such services, and this need is likely to grow in the near future.
Now, given that my company provides some such services, this may appear to be somewhat self-serving. However, I would be the first to tell you that my company would not be the right choice for many customers. It is just a question of sorting out which provider might be right for you.
I strongly recommend that you decide in advance who you would call in case of a crisis, and have their contact information readily available. If you are forced to make a choice in the heat of a major security issue, you will not have time for the proper due diligence needed to make a good choice. I also recommend that when you have a candidate, that you have them in to do an initial assessment of your information security/risk management. It is a good way to test drive a company before you really need them, and it allows them to hit the ground running if you do need help.
The following are some elements you should consider when making a selection:
Type of organization
You need to ask prospective providers the size and types or organizations they focus on. As the industry grows, so will the specialization, so you need to find a provider that fits your company. There are some very large providers that would not fit well with a smaller organization. On the other hand, if you are shopping on behalf of a large enterprise, a 3-person provider would probably not be a great fit. Look for someone that concentrates on companies of your size/type.
Compliance standards experience
If you are subject one or more compliance standards (PCI DSS, HIPAA, SOX, etc), the applicable standards(s) will be a key part of any security engagement. As such, make sure that the providers you are considering have sufficient experience with your mix.
When considering an information security provider, Google can be your best friend. Do a search on the providers you are considering, and note any information, feedback, litigation, or regulatory actions related to them. Also, ask for reference accounts from the providers, and make phone calls to the references.
While security certifications are a factor in selecting a provider, they should not in my opinion be the deciding factor. I have hired hundreds of technical personnel in my career, and have discovered in the process that there are folks who are really good at passing tests, but less competent putting that knowledge into action. In one extreme example, I hired a network engineer for a credit bureau. He had a number of Cisco certifications, and had even taught classes for Cisco. When I had to show him how make a minor change to a Cisco router during his first week, I realized that his certifications meant very little in practice.
When I look for a vendor in any area, a key element in my evaluation is their willingness to take ownership of the issues I hire them to help with. I seek vendors that "have my back", and will treat my problems as if they are their own. I do not want to watch every move they make, or have to remind them to finish their work. It is all to uncommon to find such vendors these days, so when you do, hang onto them. References are the best way to find out if your candidate provider fits this definition.
There is a certain chemistry required between a business and a vendor that is hard to define. In some ways, a vendor relationship is like a marriage, particularly so in information security, where a high degree of trust is involved. You need to find a vendor your "gut" feels good about. You need to be able to communicate well with them, and rely on them to be there when you need them.
I have office keys, alarm codes, and passwords for a number of my customers, and some of my vendors have my access information as well, because we have built a trust relationship in our work together. There are vendors I only used once or twice, and I am sure some customers who dropped me, because this chemistry/trust relationship never formed. It does not necessarily mean that either side is bad, we just didn't click.
Bottom line -- While you might choose a plumber from the yellow pages (euphemistically), the selection of an information security vendor requires care, and you will reap benefits from your selection proportional to the care you applied. Given the care required, the search should be done well before you have a security crisis.