Is it a substitution cipher or a stream cipher or both?
It is not a substitution cipher. Schneier classifies it as a stream cipher because it converts plaintext to ciphertext one bit or byte at a time, generally by XORing the plaintext with a "keystream".
In most stream ciphers the keystream is only pseudo-random, but in a classic "one-time pad" the keystream is entirely random. It can be though of as a fresh key for each message, equal in length to the plaintext, which is typically combined with the plaintext via XOR so it is easy to get plaintext back from the ciphertext with another XOR. The trick is getting the pad itself - good quality truly random keying material - to the other end of the communications channel, out-of-band....
@nealmcb is correct that a one-time pad (OTP) is a stream cipher. However, he's not correct that the defining characteristic is the quality of the randomness. What defines an OTP is:
- The key material is only used once
- The key material is the same length as the plaintext
As with any other decent cipher, the quality of your key material is paramount. However, you can implement an OTP with not-very-random numbers -- it just reduces the security of the key.
Based on the discussion below, clarification is in order.
A crypto algorithm is, strictly speaking, merely the mathematical definition of a set of cryptographic functions (encryption, decryption, and possibly signing). The definition of the algorithm may provide certain constraints, including allowable key lengths.
But choosing an algorithm is only one part of creating a secure cryptosystem. The others are:
- Selecting an attack-resistant software or hardware implementation
- Key management:
- Revocation / Destruction
So to have a secure AES based cryptosystem, you need to have a good implementation of it, and good key management.
To have a secure OTP cryptosystem, you need to have sufficiently random keys, ensure they're only used once, and have a secure distribution system for them.
In either case, poor key management doesn't mean you're not using the specified algorithm.