Question regarding using AES in CTR mode to encrypt UDP
Itay
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
tomst...@gmail.com
> 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'd use GCM or CCM mode to get authentication as well. [LTN uses
HMAC-SHA1 for that].
As for handling out of order, the simplest method is
1. Reject old packets with a soft error
2. Accept packets from the future
Another way is to have a sliding window of upto 32 packets . As you
get newer packets you slide older ones off. E.g. if you get 2 then 1
that's ok but if you get 33 then 1 that will be too old and return a
soft error.
> 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).
You have to make sure you're in sync when you start. After that you
should be ok.
> 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) ?
Why would CBC mode be better?
Tom
David Wagner
IPSec has some elegant solutions: basically, a sequence number
with a sliding window on the receive side.
Better yet, just use IPSec directly if you can, rather than trying
to re-invent the wheel. (I seem to also recall that there was
some kind of effort to build a variant of SSL that would run over
datagrams, but I don't recall how that turned out or even what the
name of the effort was. Maybe WTLS?)
David A Molnar
> some kind of effort to build a variant of SSL that would run over
> datagrams, but I don't recall how that turned out or even what the
> name of the effort was. Maybe WTLS?)
It's DTLS - "Datagram TLS." Recently published as RFC 4347:
http://www.ietf.org/rfc/rfc4347.txt?number=4347
OpenSSL has a DTLS implementation since 0.9.8 or so. I haven't
used it, but I know people in the IETF CAPWAP working group have
been working with it extensively.
-David Molnar
Joseph Ashwood
news:hnmc52tqji2rb24hb...@4ax.com...
change the packet structure to include the IV
Change the IV selection process so that B->A starts at
0x00000000000000000000000000000000
A->B starts at
0x80000000000000000000000000000000
The counters won't collide until after the birthday paradox so it's not a
problem (change keys if you reach the birthday paradox).
If this isn't for a research project of some kind, I side with Wagner
though, use something professionally designed, bulit, tested, etc.
Joe
Itay
>Itay wrote:
>> 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'd use GCM or CCM mode to get authentication as well. [LTN uses
>HMAC-SHA1 for that].
OK, I will check those out in your LTC manual, thanks :-)
>As for handling out of order, the simplest method is
>
>1. Reject old packets with a soft error
>2. Accept packets from the future
>
>Another way is to have a sliding window of upto 32 packets . As you
>get newer packets you slide older ones off. E.g. if you get 2 then 1
>that's ok but if you get 33 then 1 that will be too old and return a
>soft error.
This solves the problem of knowing which sequence number to
accept\reject
when doing the authentication (anti replay), but how does it solve the
synchronization of the CTR counters (assuming I still want to use CTR,
and I need the exact same counters in order to reverse the encryption
on peer B and get the same plaintext that peer A had before he did the
encryption) ?
>> 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).
>
>You have to make sure you're in sync when you start. After that you
>should be ok.
Can you explain in a little more detail, thanks :-)
>> 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) ?
>
>Why would CBC mode be better?
I didn't say it was better, my main question is :
can I use CTR when encrypting UDP ?
>Tom
Itay
(David Wagner) wrote:
>You might enjoy reading up on how IPSec solves this problem.
>IPSec has some elegant solutions: basically, a sequence number
>with a sliding window on the receive side.
I know and read about the sliding window solution, thanks :-)
But this doesn't solve the counter synchronization problem in CTR
(where I need the counters on the communicating peers to be exactly
the same for the encryption/decryption to work).
The sliding window is for the anti replay, so I would know if I can
accept a certain sequence number in the authentication process.
>Better yet, just use IPSec directly if you can, rather than trying
>to re-invent the wheel. (I seem to also recall that there was
>some kind of effort to build a variant of SSL that would run over
>datagrams, but I don't recall how that turned out or even what the
>name of the effort was. Maybe WTLS?)
I think you mean DTLS.
I have to create my own implementation for this project, so I can't
use IPSEC or any other protocol.
Thanks :-)
Itay
Itay
wrote:
>"Itay" <itayd...@gmail.com> wrote in message
>news:hnmc52tqji2rb24hb...@4ax.com...
>
>change the packet structure to include the IV
>Change the IV selection process so that B->A starts at
>0x00000000000000000000000000000000
> A->B starts at
>0x80000000000000000000000000000000
>The counters won't collide until after the birthday paradox so it's not a
>problem (change keys if you reach the birthday paradox).
Thanks for your advice
If I undertood you correctly, you mean to explicitly have
0x00000000000000000000000000000000
as the starting/initial IV on the B->A channel, and
0x80000000000000000000000000000000
as the starting/initial IV on the A->B channel,
Thus, A uses the IV : 0x80000000000000000000000000000000
to encrypt its first packet to B, then it adds the IV to the packet
buffer and sends it to B.
B gets the packet, first of all, it sets its IV to
0x80000000000000000000000000000000, and only then it does
the decryption (encryption)
- is that what you ment ?
>If this isn't for a research project of some kind, I side with Wagner
>though, use something professionally designed, bulit, tested, etc.
> Joe
I have to use my own implementation, thanks :-)
David Wagner
>I know and read about the sliding window solution, thanks :-)
>But this doesn't solve the counter synchronization problem in CTR
>(where I need the counters on the communicating peers to be exactly
>the same for the encryption/decryption to work).
It doesn't? Why not? Just make sure that you include the sequence
number explicitly in the packet that is transmitted.
>The sliding window is for the anti replay, so I would know if I can
>accept a certain sequence number in the authentication process.
Right.
>I think you mean DTLS.
Yup, that's it. Thanks.
Joseph Ashwood
I'm not certain I was clear, so I'm just reiterating in a different format:
You observed correctly that when A encrypts to B the initial IV is
0x80.....00 (although any such arrangement with them at points further than
the birthday paradox is fine). And that A sends the IV for that packet along
with the packet. From there B MUST read the IV from the packet (and should
make sure the packet is not replayed, and are reasonably dependable). A MUST
also keep track of the last IV it used.
The reason for the massive seperation between them is that if an IV is ever
repeated with a key the security disappears, so to avoid this and strange
sync code just start them with a huge seperation.
Joe
Itay
wrote:
B gets the packet, strips out the IV (which is also the sequence
number for the anti replay check), first of all does the anti replay
check and then uses this IV to decrypt the packet buffer
>The reason for the massive seperation between them is that if an IV is ever
>repeated with a key the security disappears, so to avoid this and strange
>sync code just start them with a huge seperation.
> Joe
I would need a separate context holding the encryption parameters for
each channel - one for A -> B and one for B -> A
Thanks :-)
Itay
(David Wagner) wrote:
>Itay wrote:
>>I know and read about the sliding window solution, thanks :-)
>>But this doesn't solve the counter synchronization problem in CTR
>>(where I need the counters on the communicating peers to be exactly
>>the same for the encryption/decryption to work).
>
>It doesn't? Why not? Just make sure that you include the sequence
>number explicitly in the packet that is transmitted.
What I meant was that the sliding window doesn't solve the counter
synchronization problem, what does solve it is (as you mentioned) to
include the counter/seqence number/IV or whatever you call it
in the packet, and the receiving side will use it forthe anti replay
check
first (with the sliding window0 and for the IV when decrypting the
packet
Volker Hetzer
> B gets the packet, strips out the IV (which is also the sequence
> number for the anti replay check), first of all does the anti replay
> check and then uses this IV to decrypt the packet buffer
>
>> The reason for the massive seperation between them is that if an IV is ever
>> repeated with a key the security disappears, so to avoid this and strange
>> sync code just start them with a huge seperation.
>> Joe
>
> I would need a separate context holding the encryption parameters for
> each channel - one for A -> B and one for B -> A
Of course, you could just as well use two different keys and start both
counters at 0. However, if you ask the user for a key, those lazy
guys will probably enter the same key for each direction, so maybe
splitting the counter space is better after all.
Just my $0.02
Volker
Volker Birk
> > 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
Kristian Gjųsteen
>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
Volker Birk
> Volker Birk <bum...@dingens.org> 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).
Kristian Gjųsteen
>In comp.security.misc Kristian Gj?steen <kristi...@math.ntnu.no> wrote:
>> Volker Birk <bum...@dingens.org> 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
D. J. Bernstein
> 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
valery
>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
Volker Birk
With chosen plaintext, you could gain information about which counter
value probably was used.
This is not possible with OFB AFAICS.
valery
course ;-).
[1] http://www.cs.ucsd.edu/users/mihir/papers/gb.html
-Valery.
http://www.harper.no/valery
valery
better security bounds than random counter CTR. See Goldwasser Bellare
"Lecture Notes on Cryptography" pp 100-110.
-Valery.
http://www.harper.no/valery
Volker Birk
> 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?
David Wagner
>In comp.security.misc D. J. Bernstein <d...@cr.yp.to> 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.
Volker Birk
> 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?
Volker Birk
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?
David Wagner
>In comp.security.misc valery <val...@harper.no> 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.
David Wagner
>> >In comp.security.misc D. J. Bernstein <d...@cr.yp.to> wrote:
>> >> For example, 128-bit keys and random
>> >> 128-bit nonces are more expensive than 256-bit keys and simple counters.
>
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.
Volker Birk
> 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.
Volker Birk
> >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?
valery
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
Volker Birk
> C-CTR has stronger security bounds than R-CTR. Read G-B lecture notes
> for details...
Thanx. I'll do.
Joseph Ashwood
news:4459...@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
Volker Hetzer
> In comp.security.misc Kristian Gj?steen <kristi...@math.ntnu.no> 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.
in the counter.
Lots of Greetings!
Volker
Volker Hetzer
> In comp.security.misc David Wagner <d...@taverner.cs.berkeley.edu> wrote:
>> Volker Birk wrote:
>>> In comp.security.misc D. J. Bernstein <d...@cr.yp.to> 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"?
> 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
tomst...@gmail.com
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