My best results have been in hiring from problem solving disciplines or areas. People who are old school hackers (in the original meaning of the term) who like to build, tweak, understand and really grok anything, such as hardware, cars, plumbing, electronics etc have always scored well in my book.
I have also noticed a strong correlation with rock music, and a large number who also like sci-fi (others have confirmed the music link, but I'm not sure whether the sci-fi is just in the folks I know)
There seem to be a high number of petrolheads in the industry as well - this could be an extension of the hacking, tweaking, modding vibe.
Academically, it makes sense to hire from a CS discipline, or one with at least some CS modules (engineering is an example), just down to the reliance on computer systems for everything, but I have also hired from many other disciplines.
As far as crypto goes, the specialists are few and far between, so I would tend to look for people who understand the core concepts, but not bother hunting for someone who can explain the mathematics behind a particular flaw. In general the crypto breaks are all around the people or the config, rather than a particular algorithm anyway.
In addition I would always take a potential new recruit to meet the team at a restaurant or pub to see how they fit in in a social setting. I see this as essential in both small and large teams.