From: Thomas on
Hello,
first post on sci.crypt, yay !

So, here is my problem : I have some cipher (AES, if that is
relevant), that needs to be used in counter (CTR) mode. I wish to
implement this myself rather than using any prebuilt library (note
that this is a coding exercise, it is not going to be used in any high-
security application).

So I've set up the encryption function, and the CTR mode works all
right. But there is a problem : how should I handle the initialization
vector that must be identical for encryption and decryption ? Should
it be secret ? What does the user typically do with it ? How is it
generated, based on the data to encrypt and the encryption key ?

Basically, what I'm asking is how to manage initialization vectors to
ensure they survive the time period between encryption and decryption.
What are the best practices ? Wikipedia and internet in general is
pretty vague about this.

Thanks !
From: Maaartin on
On Jun 19, 12:24 pm, Thomas <thomas.benet...(a)yahoo.fr> wrote:
> does it matter if the IV is not *perfectly* random, for instance say
> the IV is 128 bits long, and is obtained by generating 16 bytes from a
> noncryptographic pseudorandom number generator ? I understand it is
> bad practice but is it a fatal blow to the encrypted data or does it
> just make it a bit less secure ?

You can't use 128 bit IV together with a counter in CTR mode with AES;
where would you put it in? The IV and the counter get concatenated and
fed in the cipher. Just look at http://en.wikipedia.org/wiki/CTR_mode#Counter_.28CTR.29

The only thing you must ensure using the CTR mode is that the cipher
never gets the same input twice, you need no randomness here. For
messages shorter than 2**64 blocks you can use a 64 bit counter for
the blocks inside the message and another 64 bit counter for the IV
(so it's unique for each message). In this case you'd better don't
generate the IV randomly, since it's too short to guarantee
uniqueness.

With a the blocksize of 256 bits, generating a random 128-bit IV could
ensure uniqueness with a high probability. Using UUID would be
possible, too.

> Thanks for the idea of putting the IV into the data, I wouldn't have
> thought of it this way. But then, how would one proceed if it wasn't
> possible to actually alter the size of whatever is encrypted ?

Often, there's some unique message number which can be used as IV.
Otherwise you have a problem.

> For
> instance, is it a reasonable idea of doing a table that assigns a
> random IV to any set of encrypted data (via a hash function for
> instance), and storing this table on some portable device, and when
> decryption is done the IV can simply be looked up from the hash of the
> encrypted data ?

This can't work, since you need the IV before the encryption, so it
can't depend on the encrypted data. It can't depend on the plaintext
either, since this would make the decryption impossible. Or I
misunderstood you. Or I may be wrong, I'm no expert in crypto.
From: Thomas on
> You can't use 128 bit IV together with a counter in CTR mode with AES;
> where would you put it in? The IV and the counter get concatenated and
> fed in the cipher. Just look athttp://en.wikipedia.org/wiki/CTR_mode#Counter_.28CTR.29

I would have XORed the counter with the IV, this is also a bijective
operation.

> The only thing you must ensure using the CTR mode is that the cipher
> never gets the same input twice, you need no randomness here.

Okay, but then why not just increment a permanent IV each time a
message gets encrypted ? Say, when I freshly buy my computer, I set
the IV to zero, and each time I need to encrypt a message, I'd
increment this IV after using it. Then the IV would theorically be
unique, right ? (I'd like to see someone send 2^64 messages ...). Of
course that requires some "master IV" management, because that would
be incredibly weak if the adversary could change this value.

> For
> messages shorter than 2**64 blocks you can use a 64 bit counter for
> the blocks inside the message and another 64 bit counter for the IV
> (so it's unique for each message). In this case you'd better don't
> generate the IV randomly, since it's too short to guarantee
> uniqueness.

Ah, yes, I see now. Thanks.

> With a the blocksize of 256 bits, generating a random 128-bit IV could
> ensure uniqueness with a high probability. Using UUID would be
> possible, too.

That's what I was thinking too ... because even if the prng was
somewhat biased, it would still take a huge time to repeat with such a
large range.

> > Thanks for the idea of putting the IV into the data, I wouldn't have
> > thought of it this way. But then, how would one proceed if it wasn't
> > possible to actually alter the size of whatever is encrypted ?
>
> Often, there's some unique message number which can be used as IV.
> Otherwise you have a problem.
>
> > For
> > instance, is it a reasonable idea of doing a table that assigns a
> > random IV to any set of encrypted data (via a hash function for
> > instance), and storing this table on some portable device, and when
> > decryption is done the IV can simply be looked up from the hash of the
> > encrypted data ?
>
> This can't work, since you need the IV before the encryption, so it
> can't depend on the encrypted data. It can't depend on the plaintext
> either, since this would make the decryption impossible. Or I
> misunderstood you. Or I may be wrong, I'm no expert in crypto.

Ah. No, you understood me well, this indeed fails to work, thanks for
pointing it out.
From: rossum on
On Sat, 19 Jun 2010 02:49:36 -0700 (PDT), Thomas
<thomas.beneteau(a)yahoo.fr> wrote:

>Hello,
>first post on sci.crypt, yay !
Welcome.

>
>So, here is my problem : I have some cipher (AES, if that is
>relevant), that needs to be used in counter (CTR) mode. I wish to
>implement this myself rather than using any prebuilt library (note
>that this is a coding exercise, it is not going to be used in any high-
>security application).
>
>So I've set up the encryption function, and the CTR mode works all
>right. But there is a problem : how should I handle the initialization
>vector that must be identical for encryption and decryption ? Should
>it be secret ? What does the user typically do with it ? How is it
>generated, based on the data to encrypt and the encryption key ?
In CTR it is also called a Nonce (Number used ONCE) as well as an IV
(which is more commonly used for CBC mode).

The point is that it must *never* repeat within a given key. Using a
good random nonce is fine, but more usually it is constructed to
ensure no repetiton. With AES you have 128 bits to play with, so you
might construct a Nonce like this:

|<- 32 bits ->|<- 16 bits ->|<- 16 bits ->|<- 64 bits ->|
Message No Month "06" Day "19" Random

Month and day could be in UTF-8 (=ASCII). The counter itself would be
a separate 128 bit block and would be xor'ed with the Nonce for each
block.

It is vital that no two messages have the same Nonce/key combination.

>
>Basically, what I'm asking is how to manage initialization vectors to
>ensure they survive the time period between encryption and decryption.
>What are the best practices ? Wikipedia and internet in general is
>pretty vague about this.
>
>Thanks !
Either send it prepended to the message or send enough information for
the recipient to reconstruct it at the receiving end. This allows a
nonce to be shorter than a full random block. For example, you might
just use message number as the data sent with the actual nonce being
defined as SHA-128(message number). That technique can be useful with
short messages - a random nonce doubles the message size.

rossum

From: Maaartin on
On Jun 19, 1:14 pm, Thomas <thomas.benet...(a)yahoo.fr> wrote:
> > You can't use 128 bit IV together with a counter in CTR mode with AES;
> > where would you put it in? The IV and the counter get concatenated and
> > fed in the cipher. Just look athttp://en.wikipedia.org/wiki/CTR_mode#Counter_.28CTR.29
>
> I would have XORed the counter with the IV, this is also a bijective
> operation.

In bijective in each argument but not in both at the same time. So the
input block would get repeated and you loose.

> Okay, but then why not just increment a permanent IV each time a
> message gets encrypted ? Say, when I freshly buy my computer, I set
> the IV to zero, and each time I need to encrypt a message, I'd
> increment this IV after using it. Then the IV would theorically be
> unique, right ? (I'd like to see someone send 2^64 messages ...). Of
> course that requires some "master IV" management, because that would
> be incredibly weak if the adversary could change this value.

That's fine, except that you need to store the IV somewhere where it
persists a crash. So you need to always write the IV to the disk.
Actually, you could reduce the overhead using a sort of hi-lo
algorithm.

On Jun 19, 1:50 pm, rossum <rossu...(a)coldmail.com> wrote:
> The point is that it must *never* repeat within a given key. Using a
> good random nonce is fine, but more usually it is constructed to
> ensure no repetiton. With AES you have 128 bits to play with, so you
> might construct a Nonce like this:
>
> |<- 32 bits ->|<- 16 bits ->|<- 16 bits ->|<- 64 bits ->|
> Message No Month "06" Day "19" Random
>
> Month and day could be in UTF-8 (=ASCII). The counter itself would be
> a separate 128 bit block and would be xor'ed with the Nonce for each
> block.
>
> It is vital that no two messages have the same Nonce/key combination.

Using xor may can lead to non-unique input blocks. In this schema it's
improbable, but the message number could overflow and the 64-bit
number happen to be the same within one day or maybe one year later.
The probability is low, but worse than the security of AES. Saving
month&day in 32 bits is very wasteful, I'd use unix timestamp instead.
This way there was only one second window with a chance of conflict,
repeating every 2**32 seconds, i.e., 136 years.