Let's say I want to encrypt information in a database. What would be the best encryption algorithm to use and why. I was thinking AES, since it's widely used as a government standard, but if the database is broken into, I am unsure how long it would take to brute-force your way to the original information.
What would be the best way to store such data. I can't use hashing - the requirement is that it is encrypted.
Brute-forcing is the most stupid of attacks. It is the equivalent of a monkey repeatedly hitting a coconut with a stone until it breaks (the coconut, not the stone). If you replace the coconut with a steel safe, the monkey will be defeated. "Ultimately", the monkey could bash through the steel, if only he could hit it for (much) longer than his lifetime. But he can't: he'll be dead much before having substantially dented the steel.
What you should worry about is not brute force. A brute forcing attacker tries all possible keys until he gets lucky. It suffice to have sufficiently many possible keys to make such an attack infeasible; "many possible keys" translate to "keys sufficiently long": for symmetric encryption, a key is just a sequence of bits of a given size, and any sequence of exactly that many bits is a valid key; therefore, a 128-bit key is more than large enough to achieve appropriate resistance against brute-forcing (with a fair margin). If you use AES, then the minimum key size is 128 bits (the algorithm cannot do less anyway), so no worry there.
The issues are rather on how you use the encryption algorithm. This is a matter of subtlety and it is very easy to botch it, leaving the door open for attackers who are smarter than the average monkey. At a minimum, you should define clearly what you are trying to defend against, who will need to encrypt data, who will need to decrypt the data, and how the keys will be managed (generation, storage, access, destruction).
Of course, if you just need encryption for regulatory purposes, then just sprinkle some AES over it. It wouldn't be the first time that encryption is applied without such a thing making actual sense. Your best bet, in that case, would be Transparent Data Encryption as implemented in Oracle and SQL Server. TDE has good performance (you will not notice it) and does not alter the table format, so applications can use it transparently (hence the name). TDE protects against confidentiality breaches from attackers obtaining a read access to the relevant part of the hard disk (e.g. attackers who steal an old backup tape). That's something.
TDE, or any amount of encryption, will not magically dispel all vulnerabilities, of course. Cryptography is a science, not wizardry.
The time it takes varies widely. But you can increase the time it takes to encrypt as well as decrypt by choosing to do multiple rounds of encryption with the same key and encryption algorithm, you could even choose multiple rounds with different algorithms.
An example of the latter is Truecrypt, it allows you to do multiple different algorithms algorithms stacked together.
AES information from http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
All known attacks are computationally infeasible. For AES-128, the key can be recovered with a computational complexity of 2126.1 using bicliques. For biclique attacks on AES-192 and AES-256, the computational complexities of 2189.7 and 2254.4 respectively apply. Related-key attacks can break AES-192 and AES-256 with complexities 2176 and 299.5, respectively.
DES information from http://en.wikipedia.org/wiki/Data_Encryption_Standard
DES is now considered insecure because a brute force attack is possible (see EFF DES cracker). As of 2008, the best analytical attack is linear cryptanalysis, which requires 243 known plaintexts and has a time complexity of 239–43 (Junod, 2001).
Blowfish information at http://www.mobystar.com/_what_is_blowfish.htm
Blowfish information from http://en.wikipedia.org/wiki/Blowfish_%28cipher%29
Four rounds of Blowfish are susceptible to a second-order differential attack (Rijmen, 1997);[1] for a class of weak keys, 14 rounds of Blowfish can be distinguished from a pseudorandom permutation (Vaudenay, 1996).
Taking AES-128 as an example, you have a 128 bit key. The "stupid" brute force attack would require you to check every possible 128-bit key until you get back plain text that makes sense. There are 2^128 possible keys and hence the complexity of brute force on AES-n, where n represents the key size is O(2^n).
Now obviously there are ways to constrain the problem giving a reduced search space as cited in the previous answers but that wasn't the question :P
To give you an idea of the time I just ran an O(n^2) problem on my macbook pro 2012 and it took 1 min to solve with n=30. This implies:
n=31 -> 2mins
n=32 -> 4mins
...
n=64 -> 33 millenia!
