I'm thinking about opening up an exchange for crypto-currencies with a guarantee that deposited coins are put directly into a cold wallet. The only drawback I can see is that (so far) I don't see an easy (and secure) way to make withdrawals instantaneous.
Perhaps my background in hardware systems leads me to solutions that use physics to solve certain security problems, but to me, sending bitcoins to an unconnected computer over a unidirectional link seems trivial.
User owns a key protected by his password and your server never knows it. Another key is stored unencrypted on the web server (like in "hot" wallet). Third key is stored with your staff, encrypted by their personal password (like in "cold" wallet).
Normal withdrawal: user key and web server's key sign the transaction and it's instantly available.
Security analysis:
1. User forgot their password: he contacts staff that uses their key + web server's key to move funds to new destination.
2. Hackers have taken the web server: they see the key, but it's not enough to move anyone's funds.
3. Staff lost their keys: users still can access their funds if they still remember their passwords.
4. Hackers stole user's computer: they may instantly withdraw some amount up to an arbitrary daily limit. (Withdrawal can also be protected by 2-factor authentication.)
5. Hackers stole staff's keys (e.g. from a personal computer): they still need to break into web server. When staff realizes that keys are compromised, all funds must be moved immediately to new keys.
In other words, users have a hard proof of ownership of specific coins. All coins, no exception, are protected by two differently stored keys. So no need for hot/cold wallet difference.
If you want to block some BTC for trading, webserver will implement that easily: when you withdraw coins, it will move blocked portion to someone else's address.
You can use an HD wallet so that the online system holding an extended public key can receive BTC but not spend it. Then an offline system can sweep the incoming funds periodically.
However, these can be on different devices. Transactions can be signed on an offline machine. Also, you need just the unspent transactions to sign a new transaction, not the whole blockchain. Bitcoin Trezor works this way, http://www.bitcointrezor.com/
Is that true even if you only spend some of coins and not all the coins? I seem to remember there being something very tricky about this if you are using a paper wallet.
Let's say I have a machine that's not connected to the Internet, but I develop a serial protocol that allows the transfer of bitcoins across RS-232, and build a cable that only has the receive signals connected at my "secure" machine.
If I wanted to take it further, the "secure" machine could print that wallet onto paper or could robotically insert flash drives into a USB port (in such a way that removed keys were dropped into a bin the robot couldn't reach into.
This is only one of many ways I can think of that would allow the automatic creation of cold wallets ... the only way to attack such a system is to gain physical access.
You could still attack the stuff talking that RS232 protocol. Maybe it has a buffer overflow that allows me to gain control and change the software to write any money coming in not only to those flash drives but also out to my account (writing it to the flash drives makes it harder to detect this hack) In the limit, that doesn't require much. For example, I could flash a control LED and attempt to read it from across the street. Even if that succeeds in only a small fraction of transactions, it might still be worthwhile.
TL;dr version: anything that is connected to the outside world, no matter how small, is an attack target.
Perhaps my background in hardware systems leads me to solutions that use physics to solve certain security problems, but to me, sending bitcoins to an unconnected computer over a unidirectional link seems trivial.