Question regarding using AES in CTR mode to encrypt UDP

I am using libtomcrypt & libtomnet programmed by Tom St. Denis for my
university project.

In his libtomnet, he is using AES-128 in CTR mode.
I am interested in encrypting/decrypting packet buffers which I then
sendto/recvfrom using UDP,
but in CTR mode I have a problem synchronising the counter of the CTR
mode (or the IV) -
in UDP packets might get lost, so the synchronization between counters
on both peers is lost as well, for example :

I have two peers A & B which both share the same key and the same IV.
each time, a buffer is encrypted, the IV (or counter) is incremented
by one, and that IV is used in the encryption process.

1. A has counter/IV with a value of 1, and so does B.
2. A encrypts a buffer using the shared key and counter/IV and sends
it to B, but it gets lost (UDP).
3. A now has a new buffer to encrypt and send, it uses the key and
counter/IV of 2 to encrypt, then sends the packet.
This time B gets it, and it uses the shared key and its counter/IV
to decrypt (actually it also encrypts) the buffer.
BUT, since B's counter/IV value is 1 (and not 2 as A's counter/IV
value), the output of the decryption (encryption)
process is totally different from the plain text A encrypted.

Could someone please help me in resolving this issue(one idea I had,
was to send the counter/IV with the encrypted
message, but that increases the packets, and I would like to avoid
it).

So, how can I use CTR mode to encrypt UDP traffic (or if I cannot use
it, what mode (CBC, CFB or other )is best
recommended for working with such a protocol as UDP (unreliable) ?

Thanks :-)

Itay

Re: Question regarding using AES in CTR mode to encrypt UDP

Itay wrote:
> In his libtomnet, he is using AES-128 in CTR mode.

I'd prefer not to use CTR mode. A predictable counter there means
predictable encryption. CTR is leaking information.

While I did not cryptoanalysis on this topic, I have the feeling, that
you should not use a "counter" at all for CTR, but a pseudo random
generator, which is as secure as the idea in CFB or OFB mode to have the
same security (using a block cipher for the "random generator").

But then you could use OFB instead of CTR anyways.

> So, how can I use CTR mode to encrypt UDP traffic (or if I cannot use
> it, what mode (CBC, CFB or other )is best
> recommended for working with such a protocol as UDP (unreliable) ?

In a protocol I desigend, I have a similar problem. I'm using Twofish in
OFB mode.

I have the problem of synchronizing there, too, of course. I'm
solving this by doing key exchange reliably every time I need.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:

> Itay wrote:
>> In his libtomnet, he is using AES-128 in CTR mode.
>
> I'd prefer not to use CTR mode. A predictable counter there means
> predictable encryption. CTR is leaking information.

This revelation should be delivered to the experts that haunt sci.crypt. Tom
St Denis used to be a frequent contributor while I was there (during the
development of AES).

-- Lassi

Re: Question regarding using AES in CTR mode to encrypt UDP

Lassi Hippeläinen wrote:
> > Itay wrote:
> >> In his libtomnet, he is using AES-128 in CTR mode.
> > I'd prefer not to use CTR mode. A predictable counter there means
> > predictable encryption. CTR is leaking information.
> This revelation should be delivered to the experts that haunt sci.crypt. Tom
> St Denis used to be a frequent contributor while I was there (during the
> development of AES).

I think, this is common already, that CTR requires a non-predictable
counter to work.

And that CTR is leaking information, is easy to see, if the counter is
really counting. It's easy enough that even I can see it ;-)

Of course, sending an offset unencrypted for using OFB is leaking
information, too. But it's leaking only a small amount of information,
and the leaking is not additive.

Because I'm not a professional crypto analyst (as a matter of fact, my
job requires basic understanding of cryptography, and that's it), may
the people in sci.crypt correct me where I'm wrong ;-)

X'Post&F'up2csm, where this discussion is taking place.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>I think, this is common already, that CTR requires a non-predictable
>counter to work.

No, it does not, and that is one of its advantages. It requires no reuse
of counters to be secure. (If some value goes into the block cipher twice,
security is lost.)

Perhaps you are confusing CTR and CBC mode?

--
Kristian Gjøsteen

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc Kristian Gj?steen wrote:
> Volker Birk wrote:
> >I think, this is common already, that CTR requires a non-predictable
> >counter to work.
> No, it does not, and that is one of its advantages. It requires no reuse
> of counters to be secure. (If some value goes into the block cipher twice,
> security is lost.)

From "Counter Mode Security: Analysis and Recommendations" by David A.
McGrew:

| However, we show that attacks using precomputation can be used to
| lower the security level of AES-128 CM below the recommended strength
| for ciphers if the initial counter value is predictable.

http://www.mindspring.com/~dmcgrew/ctr-security.pdf

Do you think, David is wrong here? I cannot find a mistake in his paper.
Please show it, if you see one ;-)

BTW: David suggests to have an unpredictable counter (which was what I
was suggesting, too) or just an unpredictable initial value of the
counter. The latter I'm doubting in - because if the counter is
predictable and only the initial value is not, CTR is leaking
information, which _could_ be used additive to guess the initial value.
And then we'd have the same problem as with predictable counters.

I don't have a working attack on it (while I could imagine, that rainbow
tables could help).

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>In comp.security.misc Kristian Gj?steen wrote:
>> Volker Birk wrote:
>> >I think, this is common already, that CTR requires a non-predictable
>> >counter to work.
>> No, it does not, and that is one of its advantages. It requires no reuse
>> of counters to be secure. (If some value goes into the block cipher twice,
>> security is lost.)
>
>From "Counter Mode Security: Analysis and Recommendations" by David A.
>McGrew:
>
>| However, we show that attacks using precomputation can be used to
>| lower the security level of AES-128 CM below the recommended strength
>| for ciphers if the initial counter value is predictable.
>
>http://www.mindspring.com/~dmcgrew/ctr-security.pdf
>
>Do you think, David is wrong here? I cannot find a mistake in his paper.

There is at least one easy attack along these lines, if the initial IV
is always 0: Compute 2^85 encryptions of 0 under different keys. That
gives you a distinguishing advantage of 1/2^43 against one key (pretty
small), but a distinguishing advantage close to maximal against 2^43
keys. Alternatively, the attacker will on average be able to read 1 out
of every 2^43 messages.

This fact would show up in a concrete analysis of a system, when the
standard hybrid argument used to prove the security of the encryptions
turns the adversary's advantage of eps against the system into eps/n
against AES. It is a nice example of why one should pay attention to
the results of the concrete analysis.

An unpredictable counter will obviously block this easy attack, but
I do not immediately see any argument for why it should block all
possible attacks. Until I see such proof, I'm not sure that I care
about it. Instead, I'll suggest that if you want better security, use
a bigger key!

In summary: Counter mode does not require the initial counter value to be
unpredictable. Certain applications may require larger keys to be secure,
but that will be revealed by the security analysis of the application.

>BTW: David suggests to have an unpredictable counter (which was what I
>was suggesting, too) or just an unpredictable initial value of the
>counter. The latter I'm doubting in - because if the counter is
>predictable and only the initial value is not, CTR is leaking
>information,

How is it leaking information?

--
Kristian Gjøsteen

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
> http://www.mindspring.com/~dmcgrew/ctr-security.pdf
> Do you think, David is wrong here?

Yes. See http://cr.yp.to/papers.html#bruteforce, particularly the
discussion of input-space separation in Section 4. Adding randomness
to each nonce is more expensive and less beneficial than adding the same
amount of randomness to the key. For example, 128-bit keys and random
128-bit nonces are more expensive than 256-bit keys and simple counters.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>I think, this is common already, that CTR requires a non-predictable
>counter to work.

It's not only that it IS NOT REQUIRED to have non-redictable IV,
but in fact, use of sequential counter IV with CTR gives better IND-CPA
security bounds than what could be achieved with CTR and random IV.

See, for example Goldwasser/Micali Lecture Notes on Cryptography pp
100-110

-Valery.
http://www.harper.no/valery

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc Kristian Gj?steen wrote:
> > because if the counter is
> > predictable and only the initial value is not, CTR is leaking
> > information,
> How is it leaking information?

With chosen plaintext, you could gain information about which counter
value probably was used.

This is not possible with OFB AFAICS.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

I meant Goldwasser/Bellare "Lecture Notes on Cryptography" [1] of
course ;-).

[1] http://www.cs.ucsd.edu/users/mihir/papers/gb.html


-Valery.
http://www.harper.no/valery

Re: Question regarding using AES in CTR mode to encrypt UDP

Again, sequential counter CTR is provably IND-CPA secure and gives
better security bounds than random counter CTR. See Goldwasser Bellare
"Lecture Notes on Cryptography" pp 100-110.

-Valery.
http://www.harper.no/valery

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc D. J. Bernstein wrote:
> For example, 128-bit keys and random
> 128-bit nonces are more expensive than 256-bit keys and simple counters.

So you agree better not to have a predictable counter?

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>In comp.security.misc D. J. Bernstein wrote:
>> For example, 128-bit keys and random
>> 128-bit nonces are more expensive than 256-bit keys and simple counters.
>
>So you agree better not to have a predictable counter?

Well, I can't speak for Dan Bernstein, but I interpreted his note as
saying pretty much the exact opposite.

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc valery wrote:
> Again, sequential counter CTR is provably IND-CPA secure and gives
> better security bounds than random counter CTR. See Goldwasser Bellare
> "Lecture Notes on Cryptography" pp 100-110.

Hm... if I compare, what djb wrote:

| For example, 128-bit keys and random
| 128-bit nonces are more expensive than 256-bit keys and simple
| counters.

Then I'm confused, I must say. What's right now?

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc David Wagner wrote:
> Volker Birk wrote:
> >In comp.security.misc D. J. Bernstein wrote:
> >> For example, 128-bit keys and random
> >> 128-bit nonces are more expensive than 256-bit keys and simple counters.
> >So you agree better not to have a predictable counter?
> Well, I can't speak for Dan Bernstein, but I interpreted his note as
> saying pretty much the exact opposite.

So I'm misinterpreting, I think ;-)

"more expenive" to crack? Or in which way "more expensive"?

Hm... this is the reason, why usually I'm not discussing on sci.crypt -
I just don't have enough knowledge about cryptography to have a sensible
discussion about it.

I'm just using ready made algorithms and crypto modes I find to be seen
as secure. And usually, I'm using ready made implementations.

But I really would appreciate, if this point could be made clear -
obviously I'm not the only one, who does misinterpret or not understand
(see David's paper, for example).

The question is:

Why is a predictable counter not leading into a situation, that I can
use precomputed values to attack?

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>In comp.security.misc valery wrote:
>> Again, sequential counter CTR is provably IND-CPA secure and gives
>> better security bounds than random counter CTR. See Goldwasser Bellare
>> "Lecture Notes on Cryptography" pp 100-110.
>
>Hm... if I compare, what djb wrote:
>
>| For example, 128-bit keys and random
>| 128-bit nonces are more expensive than 256-bit keys and simple
>| counters.
>
>Then I'm confused, I must say. What's right now?

There's no contradiction. G-B are saying that using a simple counter
preserves the security of the underlying block cipher better than a
random nonce (due to the risk of nonce collisions), at roughly the same
performance level. djb is saying that, for a given security level, using
a simple counter (and longer keys) is cheaper than a random nonce (and
shorter keys) (considering the threat of precomputation attacks and
Hellman time/space tradeoff attacks). These two statements are not
contradictory. They're both right.

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk wrote:
>> >In comp.security.misc D. J. Bernstein wrote:
>> >> For example, 128-bit keys and random
>> >> 128-bit nonces are more expensive than 256-bit keys and simple counters.
>
>"more expenive" to crack? Or in which way "more expensive"?

I suspect djb meant "more expensive for the legitimate sender and
receiver", not "more expensive for the attacker". Just a guess.

>Why is a predictable counter not leading into a situation, that I can
>use precomputed values to attack?

It is. djb is saying that, if you want to prevent precomputation, it's
more effective to put more randomness into the key than to put more
randomness into the nonce/counter/IV.

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc David Wagner wrote:
> G-B are saying that using a simple counter
> preserves the security of the underlying block cipher better than a
> random nonce (due to the risk of nonce collisions)

Ah - I'd not call a mode CTR, if the nonce is _real_ random. OK, thanx
for explaining.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc David Wagner wrote:
> >Why is a predictable counter not leading into a situation, that I can
> >use precomputed values to attack?
> It is.

Then my view is correct, that one better should not use a predictable
counter, right?

> djb is saying that, if you want to prevent precomputation, it's
> more effective to put more randomness into the key than to put more
> randomness into the nonce/counter/IV.

OK, that means I _could_ have a non-predictable counter, but I also
could have a longer key (which is less expensive for encrypting and
decrypting). But why not considering a crypto mode without such
problems? Or is it unavoidable?

Say, I want to have my communication secure. I need a stream cypher,
and I'm using an hash like RIPEMD-160.

So I could use a block cypher in OFB mode, for example, and encrypting
my data with it, additionally using the hashes.

When I want to use CTR instead of OFB, then I need a longer key for the
block cypher, right?

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

you didn't get it:
C-CTR and R-CTR are different only by choice of IV.
in C-CTR IV is sequential counter (i.e. predictable)
and with R-CTR IV is choosen at random.
Both C-CTR and R-CTR are provably IND-CPA secure and ...
C-CTR has stronger security bounds than R-CTR. Read G-B lecture notes
for details...

-Valery.
http://www.harper.no/valery

Re: Question regarding using AES in CTR mode to encrypt UDP

In comp.security.misc valery wrote:
> C-CTR and R-CTR are different only by choice of IV.
> ...
> C-CTR has stronger security bounds than R-CTR. Read G-B lecture notes
> for details...

Thanx. I'll do.

Yours,
VB.
--
At first there was the word. And the word was Content-type: text/plain

Re: Question regarding using AES in CTR mode to encrypt UDP

"Volker Birk" wrote in message
news:4459e14e@news.uni-ulm.de...
> In comp.security.misc

There-in lies the problem. Wagner and Bernstein are both trying to explain
things in crypto terms, allow me to translate into general security terms
(they really are different terms, and even basic words like "nothing" used
below have different meanings).

When using CTR mode it is provably as difficult to break as the cipher
behind it. Modifying CTR mode such that the inputs have random or hidden
components gains you nothing. The entire rest of the conversation was about
the fringe cases that cryptanalysts worry about; getting that last little
tiny bit of information and edge on the opposition.
Joe

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk schrieb:
> In comp.security.misc Kristian Gj?steen wrote:
>>> because if the counter is
>>> predictable and only the initial value is not, CTR is leaking
>>> information,
>> How is it leaking information?
>
> With chosen plaintext, you could gain information about which counter
> value probably was used.
>
> This is not possible with OFB AFAICS.
The enemy is allowed to know this. Security rests in the key, not
in the counter.

Lots of Greetings!
Volker

Re: Question regarding using AES in CTR mode to encrypt UDP

Volker Birk schrieb:
> In comp.security.misc David Wagner wrote:
>> Volker Birk wrote:
>>> In comp.security.misc D. J. Bernstein wrote:
>>>> For example, 128-bit keys and random
>>>> 128-bit nonces are more expensive than 256-bit keys and simple counters.
>>> So you agree better not to have a predictable counter?
>> Well, I can't speak for Dan Bernstein, but I interpreted his note as
>> saying pretty much the exact opposite.
>
> So I'm misinterpreting, I think ;-)
>
> "more expenive" to crack? Or in which way "more expensive"?
More expensive to create.

> Why is a predictable counter not leading into a situation, that I can
> use precomputed values to attack?
Because you are supposed to use it with AES, i.e. a cipher with
at least 128bit of key.
If you were trying this with DES you'd have a problem.

Lots of Greetings!
Volker

Re: Question regarding using AES in CTR mode to encrypt UDP

D. J. Bernstein wrote:
> Volker Birk wrote:
> > http://www.mindspring.com/~dmcgrew/ctr-security.pdf
> > Do you think, David is wrong here?
>
> Yes. See http://cr.yp.to/papers.html#bruteforce, particularly the
> discussion of input-space separation in Section 4. Adding randomness
> to each nonce is more expensive and less beneficial than adding the same
> amount of randomness to the key. For example, 128-bit keys and random
> 128-bit nonces are more expensive than 256-bit keys and simple counters.

Should add that in some cases "simple counters" are not so simple.
Like when you don't have any storage to keep track if you are re-using
counters.

For CTR mode it's simply easier to use one CTR session going out and
one coming in. Both with random keys and counters (derived from a
session key via some suitably strong PRF).

Of course instead of CTR mode people should use CCM mode. Get
authentication as well :-)

Tom