Let's say there is a piece of software that uses AES CTR to encrypt different messages using the same key but with slightly different IVs.
So for example, a 16 byte IV, the 2nd 8 bytes are always the same, but the 1st 8 bytes are random.
How insecure is this?
I know that you shouldn't use the same IV and key. But do similar IVs have the same vulnerability or a different way to attack them?
As the name suggests, CTR mode works by encrypting a counter (that gets incremented with each 16-byte block) to generate a stream of random bits. That bit stream is then XOR'ed with the plaintext to create the ciphertext. The IV provides the initial value for the counter.
CTR mode is secure as long as the probability of a counter value repeating is negligible. Therefore the scheme you describe is secure under two conditions:
How small is small? Well, the birthday paradox says that if you encrypt $2^m$ messages, the probability that the random, 64-bit portion of the IV will repeat is at most $2^{2m}/2^{64}$. So if you encrypted $2^{16} = 65536$ messages, the probability of having a repeated counter is less than one in $2^{32}$; i.e., less than one in roughly four billion. In most cases, this is an acceptable risk (although some may consider it high by cryptographic standards).
The answer above is good but I would suggest that a non equal split between the Random IV size and the size of the counter would be safer. An 8 byte counter enough for $2^{64}$ 16 byte blocks, which, to be very precise, is huge. Using a 5 byte counter, for example, would still allow you to encrypt files up to $2^{40} \times 16$ bytes or about 17,592 Gigabytes. This should be plenty for most applications.
Thus 11 bytes could be used to initialize the random IV. Using the same assumption as above of up to $2^{16}$ messages under one long term key, the probability of a collision is then 1 in 144,000,000,000,000,000 as opposed to one in 4 billion.
You could adjust the relative sizes of the counter and the random IV as per your requirements. E.g. for lots of small messages (<268 MB) a 3 byte counter and a 13 byte IV could work well. For a one in a trillion risk of a collision you could encrypt $4\times 10^{19}$ small messages.
The equation for finding the probability of a collision is:
$$P = 1 - \exp( -n^2 / 2m )$$
where
The equation below finds the maximum number of messages for a given value of P the risk of a collision:
$$n = \sqrt{ - 2m \ln(1 - P) }$$
CTR mode turns a block cipher into a synchronizable/seekable stream cipher. The IV in this case is a nonce (number used once), and in general practice for a 128-bit block cipher is 96-bits (12 bytes), leaving 32-bits (4 bytes) for the block counter.
How insecure is this?
Not at all, given the following VERY important considerations:
Therefore, if you are choosing the first 8 bytes randomly, you would need to keep track of them, as randomly being identical is possible. The best way is to increment the first 8 bytes on a per message basis, modulo 2^64
But do similar IVs have the same vulnerability or a different way to attack them?
As long as the underlying block cipher (in this case AES) behaves like a random permutation, then there is not a practical attack against CTR mode. The best attack is a known plaintext attack, where the output of the cipher can be recovered, and compared with the nonce/counter to recover the key. The workload of this attack for AES in the best case is over 2^96, with massive plaintext requirements, so it is not practical. Changing keys well before 2^64 blocks is common practice.
If you are especially concerned, you can split the nonce in half, and choose half randomly. This will assure that the input to the cipher is more dissimilar, while also preventing nonce reuse. The other option is to change the key more frequently, say after 2^16 blocks, which may be very practical or very impractical depending on application.
