If I use a nonce in the protocol, does the IV still need to be random?

Question

I am creating a protocol which tries to 'store' symmetric key sessions for later. I store three things: the session_id (public), symmetric_key (private), and counter/nonce (private). With every transmission, the session_id is transmitted in the clear and used to lookup the symmetric_key. The symmetric key is used to decrypt the data. The data contains a hash(sha256) which is used to verify message contents. Then, I extract the nonce from the contents and check that it matches the stored nonce. If it does i increment the stored nonce by 1. Otherwise, the packet is fake and I toss it. Currently, I use the nonce as the IV for the symmetric_key. Is this an error? Must I use a completely random IV? Lastly, If I do use a random IV, then how do I transmit more than once? Do I need to renegotiate a new key? I am using the mcrypt library to do this.

To be clear, the client is sending: [nonce + data + hash(data+nonce)]encrypted + session_key

Thanks!

Just to clarify, you're sending back to the server, the session ID, the encrypted data, and a hash of the unencrypted contents, which includes the nonce? — Michael Mior, Oct 05 '11 at 20:50
How do you perform the initial key exchange with the client? Ideally I would suggest this be done via SSL to avoid any unexpected issues. — Michael Mior, Oct 05 '11 at 22:09
I would, but the server charges a lot more for SSL use so Im doing public/private key encryption with openssl — chacham15, Oct 05 '11 at 22:58
Could you post the code you're using for symmetric encryption? — Michael Mior, Oct 06 '11 at 11:59

score 1 · Accepted Answer · edited May 23 '17 at 12:19

I will restrict my answer to the use of random IV. I assume that you are using Cipher Block Chaining (CBC) mode that requires an IV.

Note that that the IV is not encrypted (as the receiving party needs that for decrypting the first block of data) and so if you are using nonce as the IV, instead of saying [nonce + data + hash(data+nonce)]encrypted it is more precise to say nonce + [data + hash(data+nonce)]encrypted, where + denotes concatenation.

RFC 2451 "The ESP CBC-Mode Cipher Algorithms" says "The IV MUST be chosen at random. Use of a randomly generated IV prevents generation of identical ciphertext from packets which have identical data that spans the first block of the cipher algorithm's blocksize."

In addition to being random, the IV should also be unpredictable. The earlier practice of using the last ciphertext block of the previous message as IV --- which though random is predictable --- is flawed. This flaw, however, is of concern to you only if the adversary can mount a chosen plain text attack. That is, if the attacker can send chosen plain text to be encrypted and be able to see the result. Obviously, a nonce, while unique, is predictable.

It is better to use a random IV. You can seed a PRNG and generate IVs and conservatively re-seed well before the sequence repeats. When re-seeding, it is also good idea to use key-exchange and change the symmetric key. This will ensure that for a given key you never use the same IV twice.

For more info on chosen plain text attack, see Why is using a Non-Random IV with CBC Mode a vulnerability?

The question is though, is different by 1 different enough? Meaning will 2 identical plaintexts will translate to 2 different ciphertexts? Lastly, the reason that the nonce is in the encryption is twofold: 1. prevents replay attacks, 2. the attacker cant predict the nonce and hence iv. Lastly, i found this quote from wikipedia's article on iv's: `Some cryptographic primitives require the IV only to be non-repeating, and the required randomness is derived internally. In this case, the IV is commonly called a nonce` — chacham15, Oct 16 '11 at 10:16

score 0 · Answer 2 · answered Oct 13 '11 at 20:08

0

Yes, the IV needs to still be random. If not, the system is insecure. This was the mistake that allowed the BEAST attack against openssl. You don't transmit the IV more than once, you use a new one for each message you send. Every time you encrypt a new message, pick a new IV and send [IV,ENCRYPT(k,IV,m)]

More importantly, your entire protocol is really fishy. The hash you use, doesn't actually guarantee that someone hasn't tampered with your data, since they can easily compute hash(data|nonce). If you are trying to make sure that doesn't happen, use an HMAC with a different private key.

My real advice is, don't write your own protocol. These things are really hard to do. SSL was put together by a very large number of very smart people and even then people still find flaws in it. Thankfully, those flaws are few and far between and they get fixed. Neither will be the case with anything any one person writes.

If you tell me what you are actually trying to use this for, I could point you to some existing protocols that probably already do it. It would save you the time of writing it and actually be secure.

answered Oct 13 '11 at 20:08

imichaelmiers

3,449
2
19
25

The nonce is encrypted meaning that they cannot compute hash(data+nonce). – chacham15 Oct 16 '11 at 09:57
even if it werent, the data is encrypted, so they cant get at the original. furthermore, the hash is also encrypted. therefore, even if they could recompute a hash, they cant encrypt it. – chacham15 Oct 16 '11 at 10:01
Just because the nonce is encrypted, does not mean they cannot calculate hash(newdata+nonce). You are assuming they can't use the existing hash to do that. In fact you can. Its why HMACs exist. Suppose you had hash(nonce+data). It turns out that the way the sha family of has function is constructed, you can just append data to the hash and still have it be valid. So i can generate the hash of (nonce+data+mydata) only having known the value of mydata see http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction – imichaelmiers Oct 17 '11 at 15:49
There are more complex techniques that can exploit the hash(data+nonce) in a similar way Second, since you are encrypting the data and the hash, you lead your self open to what is known as a padding oracle attack. Are there solutions to these two things that you didn't think of sure. Are there other problems they we both probably didn't think of, almost certainly. Cryptography IS HARD. Don't do it unless you have to – imichaelmiers Oct 17 '11 at 15:55
Believe me, I have no other option. I need a system which I can use in a commercial application with certain requirements which no system today can grant. Therefore, I HAVE TO build this custom system. If there were any way I could even at the expense of usability, I would, but the primary constraint given to me CANT be satisfied by the current systems. As such, I am basing what Im doing off of existing work, but that is as far as I can go. – chacham15 Oct 18 '11 at 09:17
Secondly, a padding oracle attack wont work here because you dont have a padding oracle. The reason is twofold: 1. The message has an encrypted signature meaning that transmitting random bytes wont work. 2. The other option is to use a captured message to implement the attack, however this presents 2 problems: 1. changing any part the message will invalidate the signature and cause an error, when the attacker changes only the padding the nonce will prevent the replay. Lastly, the SHA family are cryptographic hash functions, I dont see how the merkle construction applies to it – chacham15 Oct 18 '11 at 09:22

If I use a nonce in the protocol, does the IV still need to be random?

2 Answers2