[LinkSec] RE: algorithm choices - criteria
Dear DJ:
From your response it is clear that you are very much a CCM proponent. I
do appreciated that, from a vested interest point perspective of your
employer, this has merit. We need, however, be open for discussion: after
all, LinkSec is supposed to be a broader based effort for IEEE 802.
Some small comment below.
1. Single key AEAD vs. double key scheme.
Your argument is not very convincing, since - as I indicated - one can
easily generate any number of keys from just one, using a suitable key
derivation function. Moreover, in the 802.11 TGi context, it is even less
convincing, because they deploy a whole forest of keys, where less would
have sufficed, if the security design would not have needed several rounds
of "fixes".
DJ>>
At 128 bits of key/SA that is 128000 bits of
key memory and a mapping method from SAID to key material. Push that up
to 256 bits and you have 256000 bits.
DJ<<
2. Design effort with separate encryption transformation and authentication
transformation.
I agree that re-use of a single building block (your example: AES in
forward transformation mode) is beneficial. One has to consider the slow
speed of AES implementations as well, though. Sure, one can get AES-CCM to
operate fast if one wants to spend a few 100k gates. If one would like to
have a really small implementation, though, in terms of gate count, there
are however limits to what one can do with two passes of data (see point 3
below). As an example, the IEEE 802.15.4 and 802.15.3 standards use the CCM
mode (borrowed from 802.11), but for really low-cost, low clock speed
environments, one can now not implement encryption+authenticity in
software, whereas this would have been possible if the mode did not force
one to two data passes. (Not nice, considering that one can then not re-use
existing hardware and put security in software, but rather has to redesign
chips such that one can hit the data rate.)
DJ>>
A desirable property of an adopted mode or modes is that they share an
underlying crypto operation such as AES. Mixing and AES based encryption
mode with a HMAC-SHAn based authentication for example requires HW
implementation of independent crypto functions along with all the
associated design and verification effort and with increased silicon
area. When making chips, this is most unwelcome.
DJ<<
I believe the world is bigger than just a comparison between two modes that
feature in 802.11 TGi specifications... : There are plenty of designs where
decryption operations can borrow from the encryption operations, e.g., by
using a block cipher in CTR mode and any hash function (see point 3 below).
DJ>>
Keep in mind that the silicon area argument between OCB and
CCM is moot for fast applications since OCB requires a decrypt as well
as an encrypt operation and CCM requires two AES invocations.
DJ<<
3. Single pass vs. two passes.
Of course, I am aware that one can intertwine both AES-CTR and AES-CBC-MAC.
After all: both process blocks in the same direction. Conceptually,
however, this still comes down to having to process every input bit (not
part of the header) twice in an AES call rather than once.
DJ>>
The argument that CCM, or most combinations of auth and encryption based
on the same block cipher is a two pass function is not a valid one from
a hardware implementation perspective. If you assume a combinatorial
round function, AES is an operation that requires 11 rounds and 256 bits
of intermediate state to be stored between rounds. Doing CCM requires
another 128 bits for the MIC intermediate state and either a second AES
block or a sharing of the single AES block (one encrypt, one auth,
repeat until done). The [en|de]cryption and authentication proceed
simultaneously. You do not need to perform one pass over stored data for
authentication and then another for encryption although you could choose
to do it this way if you liked making your design tasks more difficult
than necessary.
DJ<<
4. Acceptance of soundness of design by cryptographic community.
History will tell. I would rather be conservative, if one has a choice, and
use a FIPS- or ANSI-approved suite. The history of 802.11 shows that
prudence would dictate using algorithms that are established, rather than
doing in-house development (802.11: WEP attack and other misery; Bluetooth:
integrity flaws because of use of CRC check, etc, etc.).
I feel that also implementers should appreciate that the CCM mode should
have specified that, in its current form, one shall not use different
length authentication tags. The attack scenario Rogaway et al describe in
their paper is trivial, yet effective and to the point.
The point of a cryptographic specification is that it should describe
exactly in which context the specification is supposed to work properly.
Claiming that in practice the mode is used in a more narrow sense might be
valid, but it should have been part of the specification, not something
that comes up to try and silence critics. One could argue the same for the
parameter choices of NTRUEncrypt (v1.0), but fact is that cryptanalysis is
performed based on specifications.
DJ>>
proofs that don't appear to be repudiated by the associated commentary.
[..]
3.4 Sublety of variable length authentication Tags
The authentication tags are not of variable length in practical use.
The authentication tags are not of variable length in practical use.
DJ<<
"Johnston, Dj"
<dj.johnston@inte
l.com> To
"Rene Struik"
09/03/2003 05:40 <RStruik@certicom.com>
PM cc
"Leech, Marcus
(EXCHANGE:FITZ:8M86)"
<mleech@NORTELNETWORKS.COM>,
<stds-802-linksec@ieee.org>
Subject
RE: algorithm choices - criteria
Rene,
You have touched upon a number of issues that I glossed over to avoid
re-running the entire 802.11i argument and writing three times as many
slides. I'll try and go through my position on these one by one. Please
keep in mind that I'm coming at this from the implementors p oint of
view.
Single key AEAD modes (including CCM and OCB) are a significant
advantage in systems with a potential multitude of simultaneous security
associations. Supporting 1000 connections over a link requires support
1000 sets of key material. At 128 bits of key/SA that is 128000 bits of
key memory and a mapping method from SAID to key material. Push that up
to 256 bits and you have 256000 bits. In RAM terms this is small, but in
rapidly accessible memory available simultaneously to multiple
instanciations of a HW crypto function, this may represent a significant
increment in silicon area and the doubling of that area due to a two key
requirement will be unwelcome.
A desirable property of an adopted mode or modes is that they share an
underlying crypto operation such as AES. Mixing and AES based encryption
mode with a HMAC-SHAn based authentication for example requires HW
implementation of independent crypto functions along with all the
associated design and verification effort and with increased silicon
area. When making chips, this is most unwelcome.
Clock rate when considering block function based crypto operations is
not a big issue for most networking standards. A simple 128 bit AES
architecture, pulling none of the clever tricks possible, can do 128
bits per 11 clocks. Some simple sums will lead to the conclusion that a
single AES block is plenty fast enough for todays wireless standards and
for the faster wireline protocols, OCB is being proposed as the
alternative with a higher top speed. This is a simple cost/speed
tradeoff. Keep in mind that the silicon area argument between OCB and
CCM is moot for fast applications since OCB requires a decrypt as well
as an encrypt operation and CCM requires two AES invocations. For fast
implementations this translated into similar area requirements. For
slower speeds, it translates into CCM being smaller since the AES
invocation rate is not a limiting factor and one AES block will do. The
faster speed of HMAC-SHAn operations is moot.
These arguments together lead one to CCM and OCB as the proposed NIST
modes with what appears to myself as a crypto-layman as the modes that
have one-key operation, a common underlying block function and security
proofs that don't appear to be repudiated by the associated commentary.
The argument that CCM, or most combinations of auth and encryption based
on the same block cipher is a two pass function is not a valid one from
a hardware implementation perspective. If you assume a combinatorial
round function, AES is an operation that requires 11 rounds and 256 bits
of intermediate state to be stored between rounds. Doing CCM requires
another 128 bits for the MIC intermediate state and either a second AES
block or a sharing of the single AES block (one encrypt, one auth,
repeat until done). The [en|de]cryption and authentication proceed
simultaneously. You do not need to perform one pass over stored data for
authentication and then another for encryption although you could choose
to do it this way if you liked making your design tasks more difficult
than necessary.
It is worth being aware that the debate in 802.11i between OCB and CCM
centered as much on MSDU vs MPDU operation as on patent encumberance.
The arguments in 802.11i that appeared to pursuade the group (I was
there) were that
1) Why chose an encumbered mode when there is a workable
alternative?
2) CCM was expressed to work over MPDUs, matching the existing
position of WEP in the standard and thus fitting better with existing
security implementations. I.E. you can fit a CCM block in the same place
in an architecture as WEP went.
I believe the first argument is the only argument from 802.11i that
pertains to LinkSec.
I did review [5] and found the arguments to be shallow for packet data
systems. So addressing sections 3 and 4 of [5] pretty much in the order
in the paper..
3.1 Efficiency Issues
We know the packet length. This is a common property of 802 systems. We
know the storage requirements of CCM, so the lack of knowledge of
storage requirement doesn't contribute to CCM's non 'on-line'ness since
we do know. So there is no issue with not being 'on-line' for any 802
packet data standard I can think of. We are defining an 802 Link
Security spec, not a general security algorithm, so this is an
appropriate technology choice.
Word Alignment: In any packet data hardware, you can be sure that the
word alignment will be dealt with prior to passing data to a block
function. Packet headers tend to destroy word alignment of data fields
anyway and so this is a problem to be addressed at a more general MAC
implementation level that the crypto function.
Can't pre-process static AD: For lower speed protocols, as described
above, the additional invocations for handling static AD are moot. For
faster systems, OCB is being proposed. There is no conflict here.
3.2 Parameterization
'An Innapropriate Parameter' and 'Tradeoff between Nonce Length and
Maximum Message Length: The author describes the tradeoff between the
counter length/dlen length and the nonce length as being something that
the user should not have to deal with. The user does not have to deal
with it (unless 802 is the user), this tradeoff (expressed as a
parameter) gets set to a fixed value in standardized use based on the
properties of the packet system it is operating on. A counter of 16 bits
is sufficient for the maximum packet lengths in 802. Being able to
minimize the counter length for the circumstances of the packet system
allows the space for the nonce to be maximized. Maximizing the nonce
size minimized the rekeying rate and this is a good thing.
'Marginal Utility With Random Nonces' : CCM works with a incrementing
nonce. If large nonces are possible and thus might support random nonces
then that doesn't mean that it's a good idea. I'm not sure how one can
determine that this was the intent of the authors. From an
implementation point of view, generating cryptographic quality random
numbers is a pig. Generating them fast for supplying nonces is
particularly hard. Criticising a mode that works fine with contiguous
nonces for being able to support random nonces seems specious.
Byte orientation: 802 is expressed over octets. There is no conflict
here.
3.3 Complexity
The complexity of the bit manipulations is moot. This is a difference in
the level of complexity between not complex and a tiny bit complex. The
bit twiddling referred to does not even exist in an implementation with
a fixed AD space as in the proposed 802.16, 802.11 and LinkSec use.
Missing abstraction boundary : This sounds like playing with semantics.
Why is this relevant to the correctness of the security proof?
Missing Abstraction boundary, Illustration 2: Number of block cipher
calls. As described above, the small difference in the number of calls
is moot for slower applications and OCB is being proposed for faster
applications.
3.4 Sublety of variable length authentication Tags
The authentication tags are not of variable length in practical use. The
mode allows the length of the authentication tag to be chosen. Proposed
uses of CCM in 802 pick a length an fix it. This is as it should be
since different protocols have different quantities of AD to be
authenticated but the length tends to remain static within a single
technology (such as 802.11 or 802.16).
Interpretation : The author makes an interpretation and then attacks
that interpretation. From a standards setting point of view, the
flexibility in tag length is welcome, since CCM can be moulded to the
needs of an individual MAC without going outside the terms of the
security guarantees offered by the mode.
3.5 Meaningless Security Claims : Why should the existence of an ill
informed security claims lessen the validity of Jonsson's security
proof? Clearly they don't. This is not a valid criticism.
4 Conclusion : They find CCM not to be the best choice for a general
purpose standard. This may be so, but it appears to be a fine choice for
a packet data system where the speed requirements are not onerous. The
size of the data needing authentication may be greater than the size of
the data needing encryption, where patent claims can be avoided and
where small implementations using a common underlying crypto function
with a minimum of keying material is desireable. A mode EAX is proffered
but I have failed to find this on either the NIST web site or with my
finest Googling attempts.
That's all I can think of for now..
Regards,
DJ
David Johnston
Intel Corporation
Chair, IEEE 802 Handoff ECSG
Email : dj.johnston@intel.com
Tel : 503 380 5578 (Mobile)
Tel : 503 264 3855 (Office)
> -----Original Message-----
> From: Rene Struik [mailto:RStruik@certicom.com]
> Sent: Wednesday, September 03, 2003 12:36 PM
> To: Johnston, Dj
> Cc: Leech, Marcus (EXCHANGE:FITZ:8M86);
> owner-stds-802-linksec@majordomo.ieee.org; stds-802-linksec@ieee.org
> Subject: algorithm choices - criteria
>
>
>
>
>
>
> Dear DJ:
>
> Please see below for relevant references to the CCM mode. The
> CCM mode does
> not have any particular advantages compared to a secure
> composition of an
> encryption transformation and a data authenticity
> transformation, except
> maybe for the use of a single key for both transformation
> (small advantage,
> since one can easily derive two keys from one using a kdf
> function). CCM
> requires two message passes (once for authenticity, once for
> encryption),
> requires the length of the message to be known beforehand
> (thus requiring
> buffering), and other disadvantages. I would advise anyone
> promoting the
> use of CCM to consult reference [5] below for a critique. In
> my view, CCM's
> claim to fame is that it was convenient for the 802.11 TGi
> community at the
> time, while it struggled with adopting the far more efficient OCB (and
> paying a very modest royalty fee) or go for suggested
> "royalty-free" status
> of CCM and pay a performance penalty. There is not much else to it and
> there are numerous other designs available, if one does not want to be
> IEEE-centered. If one would like to adopt a so-called AEAD
> scheme (of which
> CCM is only an example), I would advise considering also
> alternatives in
> that space (see, e.g., NIST's mode of operation website, see
> weblink under
> [4]).
>
> For very high data rates, the implementation of an AEAD scheme (that
> requires two data passes) might have a higher hardware
> implementation cost
> than just implementing the composition of an encryption transformation
> (such as AES-CTR) and an authentication transformation (such as
> HMAC-SHA256), for the cost of the latter is mainly dominated
> by the cost
> of performing AES operations (SHA-256 is much faster than AES
> in hardware).
> Thus, CCM might require a higher clockrate or a higher gate
> count, to hit
> the required data rate.
>
> In general, I would like to advise against adopting any
> cipher that has not
> established itself for a reasonably long enough time in the
> cryptographic
> community. Furthermore, proper selection criteria include:
> - cryptographic merits
> - standardization and endorsement by bodies (e.g., FIPS, ANSI)
> - implementation cost in software
> - implementation cost in hardware
> - re-use of implementation for both encryption and decryption
> transformation
> - RAM usage for keying material
>
> I did not see any of the above criteria applied in the minutes of
> yesterday's (Sep 2, 2003) conference call LinkSec. In fact, I
> do believe
> that the applied crypto suite should be considered as a
> black box, and the
> specification should just describe what the format of inputs
> and outputs
> is. Please also see
> http://eprint.iacr.org/2003/177/ and other publications in
> the IACR ePrint
> Archive for proper guidance.
>
> Rene
> (cryptographer)
>
> ----------------
> 1.1.1 References
> [1] FIPS Pub 113, Computer Data Authentication, Federal Information
> Processing Standards Publication 113, US Department of
> Commerce/N.I.S.T.,
> May 30, 1985. Available from http://csrc.nist.gov/.";
> [2] R. Housley, D. Whiting, N. Ferguson, Counter with CBC-MAC (CCM),
> submitted to N.I.S.T., June 3, 2002. Available from
> http://csrc.nist.gov/encryption/modes/proposedmodes/.
> [3] J. Jonsson, On the Security of CTR + CBC-MAC, in Proceedings of
> Selected Areas in Cryptography - SAC 2002, K. Nyberg, H. Heys, Eds.,
> Lecture Notes in Computer Science, Vol. 2595, pp. 76-93,
> Berlin: Springer,
> 2002.
> [4] J. Jonsson, On the Security of CTR + CBC-MAC, NIST Mode
> of Operation
> - Additional CCM Documenta-tion. Available from
> http://csrc.nist.gov/encryption/modes/proposedmodes/.
> [5] P. Rogaway, D. Wagner, A Critique of CCM, IACR ePrint Archive
> 2003-070, April 13, 2003.
>
>
>
>
> "Johnston, Dj"
>
> <dj.johnston@inte
>
> l.com>
> To
> Sent by: "Leech, Marcus
>
> owner-stds-802-li (EXCHANGE:FITZ:8M86)"
>
> nksec@majordomo.i
> <mleech@NORTELNETWORKS.COM>,
> eee.org
> <stds-802-linksec@ieee.org>
>
> cc
>
>
> 09/03/2003 02:49
> Subject
> PM RE: [LinkSec]
> Preliminary view of
> header format
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> Marcus,
>
> The birthday limit is not a problem with CCM. The MIC is encrypted, so
> passive collision farming is prevented.
>
> An active attacker is forced to guess MICs and try them, so they don't
> have the advantage of the birthday paradox, they need to try 2^64
> attempts to expect a packet to be received with a valid MIC, but the
> attacker would have no control over the contents and the
> victim might be
> expected to notice 2^64 MIC violations coming in and rekey ahead of
> time.
>
> This is why the PN/IV length can be greater than n/2 bits
> where the MIC
> length is n bits.
>
> I haven't looked at the details but the same argument seems
> to apply to
> OCB.
>
> And yes, I did ask a cryptographer before sending this.
>
> DJ
>
> David Johnston
> Intel Corporation
> Chair, IEEE 802 Handoff ECSG
>
> Email : dj.johnston@intel.com
> Tel : 503 380 5578 (Mobile)
> Tel : 503 264 3855 (Office)
>
> > -----Original Message-----
> > From: Leech, Marcus (EXCHANGE:FITZ:8M86)
> > [mailto:mleech@NORTELNETWORKS.COM]
> > Sent: Tuesday, September 02, 2003 12:38 PM
> > To: stds-802-linksec@ieee.org
> > Subject: [LinkSec] Preliminary view of header format
> >
> >
> >
> > Here's a preliminary view:
> >
> > SAID|IV|PAYLOAD|MIC
> >
> > SAID = 4 bytes Security Association Identifier
> > IV = Initialization Vector, 4-16 bytes, depending on ciphersuite
> > PAYLOAD = variable length
> > MIC = Message Integrity Code, 8-16 bytes, depending on ciphersuite
> >
> >
> > The SAID could be compressed to a single octet if there is
> > other implicit context
> > "lying around" that can uniquely identify this security
> > association. It's not
> > clear to me that is possible across all technologies we're
> > talking about here,
> > so making it 4 bytes (32-bits) would be consistent with
> > 802.10, and IPSec.
> >
> > Given the birthday paradox, I'm inclined to conservatism, and
> > perhaps that
> > 8-16 bytes for MIC should be 10-16 bytes. It would
> > probably be prudent
> > to make a statement in each ciphersuite that negotiation
> of new keys
> > (and consequent SAID) should begin when 2**((N/2)-1)
> > messages have been
> > transmitted under the current key, where N is the MIC
> size in bits.
> >
> > --
> >
> ----------------------------------------------------------------------
> > Marcus Leech Mail:
> > Advisor Phone: (ESN)
> > 393-9145 +1 613 763 9145
> > Security Architecture and Planning Fax: (ESN)
> > 393-2754 +1 613 763 2754
> > Nortel Networks mleech@nortelnetworks.com
> > -----------------Expressed opinions are my own, not my
> > employer's------
> >
>
>