AES Modes

[David A. McGrew]

DJ,

On Oct 13, 2004, at 10:59 AM, dj at deadhat.com wrote:

> On the IEEE 802 standards track, CCM and GCM have traction. CCM has 
> been
> in 802.11 for a while and the 802.16-2004 was published last week,
> supplanting the broken DES-CBC mode with AES-CCM. For wireless 
> systems, we
> know and like CCM and it's going to take a lot to oust it.
>
> I'm aware of a handful of other wireless protocols in development that
> appear to be all headed the CCM way.
>
> GCM proposed for 802.1ae linksec. This is the 'fast' mode for wired 
> ethernet.
>
> For packetised traffic below 1Gbps, CCM works just great. The CTR and 
> CBC
> parts of CCM run in parallel in hardware, making the basic latency = 1 
> AES
> (which is 11 clocks in a simple implementation). With a bit of HW loop
> unrolling and pipelining, I can do CCM upto several gigabits.
>
> CCM nicely matches the structure of packets. Namely
> 1) Get header -> Process additional authenticated data
> 2) Get payload -> Process MAC and encryption in parallel.
> So it is not a bear to implement in a typical communications datapath 
> IC,
> where things are presented to you in this order.
>
> GCM allows block level parallelism up to a point.

I'm not sure what you mean here.  Is there some limitation that you 
have in mind?

> Hence enabling me to put
> lots of parallel AES blocks on a chip and go at multi gigabits without
> breaking a sweat. It does however have all that Galois arithmetic to do
> per block, which increases the path depth a bit.
>
> There is however a fundamental speed problem with packet oriented AES
> based modes. The parallelism you can achieve on things like GCM 
> requires
> that you have multiple blocks to run in parallel. If I get a large 
> number
> of small packets, each < 128 bits long, then there's nothing to do in
> parallel at the block level and so my speed limit is determined by how
> fast I can run 11 rounds of AES.

I'm not quite sure what you mean here, but GCM can be implemented with 
a single AES pipeline and a single GF(2^128) multiplier such that data 
from multiple packets can be in the pipeline at the same time.  In 
fact, this was a design requirement for GCM; the other authenticated 
encryption modes lack this property and their performance suffers for 
it when used for packet encryption at high data rates.  There is an 
analysis of this issue in Section 3.1. of 
http://eprint.iacr.org/2004/193/ that includes a comparison between 
GCM, CWC, and OCB.  Here is the result: GCM is the only authenticated 
encryption mode that doesn't stall its AES pipeline each time a new 
packet comes in, and this enables it to go twice as fast as CWC and 
three times as fast as OCB on Internet data, in the case in which a 
single AES pipeline is used.  (Other modes aren't in the contest, since 
they use chaining.)

>
> This may come to bite us in the future and when we start having to 
> protect
> data pushing the terabits, we either need larger packets or something
> different in the crypto. One way is to protect over large packet
> aggregates, but no 802 level protocol is set up to support it. Stream
> ciphers look attractive here, we can make them go *really* fast in
> hardware.

CTR and GCM can be fully pipelined; I'm not sure what a stream cipher 
could do that would be better.  I guess one potential improvement would 
be lower latency due to reduced pipeline depth.  But I don't understand 
where a stream cipher would get the increase in data throughput that 
you're alluding to.

Best regards,

David

>
> Another frustrating aspect of the current crop of modes is frame
> expansion. Throwing in an 8 byte nonce and an 8 byte ICV per packet is 
> a
> heavy overhead. Deriving nonces from the protocol state is generally 
> not
> wise since the frame counts are either non existant (802.3, 802.11) or 
> not
> secured (802.16).
>
> In the coming years, I would like to see link protocols (I.E. 802.*) 
> move
> link security down to the PHY, to protect management and data traffic
> equally, to secure the protocol state as well as data and so to reduce
> packet overhead. I would also like to see the standardized crypto and
> protocols be structured to work over larger aggregates of packets,
> protecting the structure of transmission as well as the content and
> allowing much greater levels of parallelism in the HW implementations.
>
> Obviously, none of this is very relevant above layer 2.
>
> Regards,
> DJ
>
>>> From: Ian Grigg <iang at systemics.com>
>>> Sent: Oct 10, 2004 11:11 AM
>>> To: Metzdowd Crypto <cryptography at metzdowd.com>
>>> Subject: AES Modes
>>
>>
>>> I'm looking for basic mode to encrypt blocks (using AES)
>>> of about 1k in length, +/- an order of magnitude.  Looking
>>> at the above table (2nd link) there are oodles of proposed
>>> ones.
>>
>>> It would be nice to have a mode that didn't also require
>>> a separate MAC operation - I get the impression that
>>> this is behind some of the proposals?
>>
>> I think CCM is just about perfect for this goal.  The MAC isn't free, 
>> but
>> it's integrated into the chaining mode.  There are also some patented
>> modes that provide a MAC for almost no extra computation(OCB, IACBC), 
>> and
>> some proposed modes that combine an efficient, parallelizeable MAC 
>> with
>> encryption in a secure way (CWC,GCM), though none of these are 
>> standards
>> yet.
>>
>>> iang
>>
>> --John
>>
>> ---------------------------------------------------------------------
>> The Cryptography Mailing List
>> Unsubscribe by sending "unsubscribe cryptography" to
>> majordomo at metzdowd.com
>>
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to 
> majordomo at metzdowd.com
>


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com